package com.cty._04_Optimization._44_DigitsInSequence;

/**
 * @Auther: cty
 * @Date: 2020/7/18 7:10
 * @Description: 面试题44：数字序列中某一位的数字
 * 题目：数字以0123456789101112131415…的格式序列化到一个字符序列中。在这
 * 个序列中，第5位（从0开始计数）是5，第13位是1，第19位是4，等等。请写一
 * 个函数求任意位对应的数字。
 * @version: 1.0
 */
public class DigitsInSequence {

    public static int digitAtIndex(int index){
        if(index < 0)
            return -1;

        int digits = 1;
        while(true){
            int numbers = countOfIntegers(digits);

            if(index < numbers*digits)
                return digitAtIndex(index, digits);

            index -= numbers*digits;
            digits++;
        }  // end while
    }  // end digitsAtIndex()

    // 计算digits位数的个数
    private static int countOfIntegers(int digits){
        if(digits == 1)
            return 10;

        return 9*(int)Math.pow(10, digits-1);
    }  // end countOfIntegers()

    // 根据index值及其所在位数，计算字符序列中的第index位数字
    private static int digitAtIndex(int index, int digits){
        if(digits == 1)
            return index;

        int beginNumber = (int)Math.pow(10, digits-1);
        int number = beginNumber + index/digits;
        int indexFromRight = digits - index % digits;
        for(int i=1; i<indexFromRight; i++)
            number /= 10;

        return number%10;
    }  // end digitAtIndex()

}  // end class
